On Binary de Bruijn Sequences from LFSRs with Arbitrary Characteristic Polynomials

摘要

We propose a construction of de Bruijn sequences by the cycle joining methodfrom linear feedback shift registers (LFSRs) with arbitrary characteristicpolynomial $f(x)$. We study in detail the cycle structure of the set$\Omega(f(x))$ that contains all sequences produced by a specific LFSR ondistinct inputs and provide an efficient way to find a state of each cycle. Ourstructural results lead to an efficient algorithm to find all conjugate pairsbetween any two cycles, yielding the adjacency graph. The approach provides apractical method to generate a large class of de Bruijn sequences. Manyrecently-proposed constructions of de Bruijn sequences are shown to be specialcases of our construction.